
/*-------------------------------------------------------------------------
 *
 * nodeSetOp.c
 *	  处理INTERSECT和EXCEPT选择的例程
 *
 * SetOp节点的输入由两个关系的元组组成，这些元组被组合成一个数据集，并添加了一个垃圾属性，显示每个元组来自哪个关系。在SETOP_SORTED模式下，输入进一步根据所有分组列（即所有非垃圾属性）进行了排序。SetOp节点扫描每组相同的元组，以确定每个输入关系中有多少元组。然后发出SQL规范所要求的INTERSECT、INTERSECT ALL、EXCEPT或EXCEPT ALL的输出是一件简单的事情。
 *
 * 在SETOP_HASHED模式下，输入没有特定顺序，除了我们知道来自一个输入关系的所有元组将在来自另一关系的所有元组之前。规划器保证，第一个输入关系是EXCEPT的左侧关系，并尝试使较小的输入关系在INTERSECT中首先出现。我们在内存中构建一个哈希表，每个条目对应一组相同的元组，并计算来自每个关系的元组数量。在查看所有输入后，我们扫描哈希表，并使用这些计数生成正确的输出。我们可以避免为仅出现在第二个输入关系的任何元组创建哈希表条目，因为它们不会产生任何输出。
 *
 * 此节点类型不用于UNION或UNION ALL，因为这些可以更便宜地实现（不需要垃圾属性来识别源关系）。
 *
 * 请注意，SetOp不进行任何资格检查或投影。交付的输出元组只是每个输入组中第一个到达元组的副本。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/executor/nodeSetOp.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/htup_details.h"
#include "executor/executor.h"
#include "executor/nodeSetOp.h"
#include "miscadmin.h"
#include "utils/memutils.h"



/*
 * SetOpStatePerGroupData - 每组工作状态
 *
 * 这些值是工作状态，在输入元组组开始时初始化，并针对每个输入元组进行更新。
 *
 * 在 SETOP_SORTED 模式下，我们只需要一个这些结构，并将其保存在计划状态节点中。在 SETOP_HASHED 模式下，哈希表为每个元组组包含一个这些结构。
 */
typedef struct SetOpStatePerGroupData
{
	long		numLeft;		/* 组中左输入重复的数量 */
	long		numRight;		/* 组中的右输入重复的数量 */
}			SetOpStatePerGroupData;


static TupleTableSlot *fc_setop_retrieve_direct(SetOpState *fc_setopstate);
static void fc_setop_fill_hash_table(SetOpState *fc_setopstate);
static TupleTableSlot *fc_setop_retrieve_hash_table(SetOpState *fc_setopstate);


/*
 * 为一组新的输入值初始化状态。
 */
static inline void fc_initialize_counts(SetOpStatePerGroup fc_pergroup)
{
	fc_pergroup->numLeft = fc_pergroup->numRight = 0;
}

/*
 * 为一个输入元组推进适当的计数器。
 */
static inline void fc_advance_counts(SetOpStatePerGroup fc_pergroup, int fc_flag)
{
	if (fc_flag)
		fc_pergroup->numRight++;
	else
		fc_pergroup->numLeft++;
}

/*
 * 从输入元组中获取“标志”列。
 * 这是一个整数列，左侧的值为0，右侧的值为1。
 */
static int fc_fetch_tuple_flag(SetOpState *fc_setopstate, TupleTableSlot *fc_inputslot)
{
	SetOp	   *fc_node = (SetOp *) fc_setopstate->ps.plan;
	int			fc_flag;
	bool		fc_isNull;

	fc_flag = DatumGetInt32(slot_getattr(fc_inputslot,
									  fc_node->flagColIdx,
									  &fc_isNull));
	Assert(!fc_isNull);
	Assert(fc_flag == 0 || fc_flag == 1);
	return fc_flag;
}

/*
 * 初始化哈希表为空。
 */
static void fc_build_hash_table(SetOpState *fc_setopstate)
{
	SetOp	   *fc_node = (SetOp *) fc_setopstate->ps.plan;
	ExprContext *fc_econtext = fc_setopstate->ps.ps_ExprContext;
	TupleDesc	fc_desc = ExecGetResultType(outerPlanState(fc_setopstate));

	Assert(fc_node->strategy == SETOP_HASHED);
	Assert(fc_node->numGroups > 0);

	fc_setopstate->hashtable = BuildTupleHashTableExt(&fc_setopstate->ps,
												   fc_desc,
												   fc_node->numCols,
												   fc_node->dupColIdx,
												   fc_setopstate->eqfuncoids,
												   fc_setopstate->hashfunctions,
												   fc_node->dupCollations,
												   fc_node->numGroups,
												   0,
												   fc_setopstate->ps.state->es_query_cxt,
												   fc_setopstate->tableContext,
												   fc_econtext->ecxt_per_tuple_memory,
												   false);
}

/*
 * 我们已完成对元组组的处理。决定发出多少个（如果有的话）
 * 其代表行的副本，并将计数存储到numOutput中。
 * 此逻辑直接来源于SQL92规范。
 */
static void set_output_count(SetOpState *fc_setopstate, SetOpStatePerGroup fc_pergroup)
{
	SetOp	   *fc_plannode = (SetOp *) fc_setopstate->ps.plan;

	switch (fc_plannode->cmd)
	{
		case SETOPCMD_INTERSECT:
			if (fc_pergroup->numLeft > 0 && fc_pergroup->numRight > 0)
				fc_setopstate->numOutput = 1;
			else
				fc_setopstate->numOutput = 0;
			break;
		case SETOPCMD_INTERSECT_ALL:
			fc_setopstate->numOutput =
				(fc_pergroup->numLeft < fc_pergroup->numRight) ?
				fc_pergroup->numLeft : fc_pergroup->numRight;
			break;
		case SETOPCMD_EXCEPT:
			if (fc_pergroup->numLeft > 0 && fc_pergroup->numRight == 0)
				fc_setopstate->numOutput = 1;
			else
				fc_setopstate->numOutput = 0;
			break;
		case SETOPCMD_EXCEPT_ALL:
			fc_setopstate->numOutput =
				(fc_pergroup->numLeft < fc_pergroup->numRight) ?
				0 : (fc_pergroup->numLeft - fc_pergroup->numRight);
			break;
		default:
			elog(ERROR, "unrecognized set op: %d", (int) fc_plannode->cmd);
			break;
	}
}


/* ----------------------------------------------------------------
 *		ExecSetOp
 * ----------------------------------------------------------------
 */
static TupleTableSlot *			/* 返回：一个元组或 NULL */
fc_ExecSetOp(PlanState *fc_pstate)
{
	SetOpState *fc_node = castNode(SetOpState, fc_pstate);
	SetOp	   *fc_plannode = (SetOp *) fc_node->ps.plan;
	TupleTableSlot *fc_resultTupleSlot = fc_node->ps.ps_ResultTupleSlot;

	CHECK_FOR_INTERRUPTS();

	/*
	 * 如果先前返回的元组需要返回多次，
	 * 则继续返回它。
	 */
	if (fc_node->numOutput > 0)
	{
		fc_node->numOutput--;
		return fc_resultTupleSlot;
	}

	/* 否则，如果我们没有组了，就完成了 */
	if (fc_node->setop_done)
		return NULL;

	/* 根据正确的策略获取下一个元组组 */
	if (fc_plannode->strategy == SETOP_HASHED)
	{
		if (!fc_node->table_filled)
			fc_setop_fill_hash_table(fc_node);
		return fc_setop_retrieve_hash_table(fc_node);
	}
	else
		return fc_setop_retrieve_direct(fc_node);
}

/*
 * 非哈希情况下的ExecSetOp
 */
static TupleTableSlot * fc_setop_retrieve_direct(SetOpState *fc_setopstate)
{
	PlanState  *fc_outerPlan;
	SetOpStatePerGroup fc_pergroup;
	TupleTableSlot *fc_outerslot;
	TupleTableSlot *fc_resultTupleSlot;
	ExprContext *fc_econtext = fc_setopstate->ps.ps_ExprContext;

	/*
	 * 从节点获取状态信息
	 */
	fc_outerPlan = outerPlanState(fc_setopstate);
	fc_pergroup = (SetOpStatePerGroup) fc_setopstate->pergroup;
	fc_resultTupleSlot = fc_setopstate->ps.ps_ResultTupleSlot;

	/*
	 * 我们循环检索组，直到找到一个应该返回的
	 */
	while (!fc_setopstate->setop_done)
	{
		/*
		 * 如果我们还没有新组的第一个元组，从外部计划中获取它。
		 */
		if (fc_setopstate->grp_firstTuple == NULL)
		{
			fc_outerslot = ExecProcNode(fc_outerPlan);
			if (!TupIsNull(fc_outerslot))
			{
				/* 复制第一个输入元组 */
				fc_setopstate->grp_firstTuple = ExecCopySlotHeapTuple(fc_outerslot);
			}
			else
			{
				/* 外部计划完全没有产生任何元组 */
				fc_setopstate->setop_done = true;
				return NULL;
			}
		}

		/*
		 * 将复制的第一个输入元组存储在为其保留的元组表槽中。
		 * 当从槽中清除时，将删除该元组。
		 */
		ExecStoreHeapTuple(fc_setopstate->grp_firstTuple,
						   fc_resultTupleSlot,
						   true);
		fc_setopstate->grp_firstTuple = NULL;	/* 不要保留两个指针 */

		/* 为新的输入元组组初始化工作状态 */
		fc_initialize_counts(fc_pergroup);

		/* 计算第一个输入元组 */
		fc_advance_counts(fc_pergroup,
					   fc_fetch_tuple_flag(fc_setopstate, fc_resultTupleSlot));

		/*
		 * 扫描外部计划，直到耗尽或越过组边界。
		 */
		for (;;)
		{
			fc_outerslot = ExecProcNode(fc_outerPlan);
			if (TupIsNull(fc_outerslot))
			{
				/* 不再有外部计划元组可用 */
				fc_setopstate->setop_done = true;
				break;
			}

			/*
			 * 检查我们是否越过了组边界。
			 */
			fc_econtext->ecxt_outertuple = fc_resultTupleSlot;
			fc_econtext->ecxt_innertuple = fc_outerslot;

			if (!ExecQualAndReset(fc_setopstate->eqfunction, fc_econtext))
			{
				/*
				 * 保存下一组的第一个输入元组。
				 */
				fc_setopstate->grp_firstTuple = ExecCopySlotHeapTuple(fc_outerslot);
				break;
			}

			/* 仍在同一组中，因此计数此元组 */
			fc_advance_counts(fc_pergroup,
						   fc_fetch_tuple_flag(fc_setopstate, fc_outerslot));
		}

		/*
		 * 完成扫描输入元组组。看看我们是否应该发出任何结果元组的副本，
		 * 如果是，则返回第一个副本。
		 */
		set_output_count(fc_setopstate, fc_pergroup);

		if (fc_setopstate->numOutput > 0)
		{
			fc_setopstate->numOutput--;
			return fc_resultTupleSlot;
		}
	}

	/* 没有更多组 */
	ExecClearTuple(fc_resultTupleSlot);
	return NULL;
}

/*
 * 哈希情况下的ExecSetOp：阶段1，读取输入并构建哈希表
 */
static void fc_setop_fill_hash_table(SetOpState *fc_setopstate)
{
	SetOp	   *fc_node = (SetOp *) fc_setopstate->ps.plan;
	PlanState  *fc_outerPlan;
	int			fc_firstFlag;
	bool		fc_in_first_rel PG_USED_FOR_ASSERTS_ONLY;
	ExprContext *fc_econtext = fc_setopstate->ps.ps_ExprContext;

	/*
	 * 从节点获取状态信息
	 */
	fc_outerPlan = outerPlanState(fc_setopstate);
	fc_firstFlag = fc_node->firstFlag;
	/* 验证规划程序没有搞错 */
	Assert(fc_firstFlag == 0 ||
		   (fc_firstFlag == 1 &&
			(fc_node->cmd == SETOPCMD_INTERSECT ||
			 fc_node->cmd == SETOPCMD_INTERSECT_ALL)));

	/*
	 * 处理每个外部计划元组，然后获取下一个，直到我们
	 * 耗尽外部计划。
	 */
	fc_in_first_rel = true;
	for (;;)
	{
		TupleTableSlot *fc_outerslot;
		int			fc_flag;
		TupleHashEntryData *fc_entry;
		bool		fc_isnew;

		fc_outerslot = ExecProcNode(fc_outerPlan);
		if (TupIsNull(fc_outerslot))
			break;

		/* 确定是左侧还是右侧输入 */
		fc_flag = fc_fetch_tuple_flag(fc_setopstate, fc_outerslot);

		if (fc_flag == fc_firstFlag)
		{
			/* （仍然）在第一个输入关系中 */
			Assert(fc_in_first_rel);

			/* 查找或构建该元组组的哈希表条目 */
			fc_entry = LookupTupleHashEntry(fc_setopstate->hashtable, fc_outerslot,
										 &fc_isnew, NULL);

			/* 如果是新元组组，初始化计数 */
			if (fc_isnew)
			{
				fc_entry->additional = (SetOpStatePerGroup)
					MemoryContextAlloc(fc_setopstate->hashtable->tablecxt,
									   sizeof(SetOpStatePerGroupData));
				fc_initialize_counts((SetOpStatePerGroup) fc_entry->additional);
			}

			/* 提升计数 */
			fc_advance_counts((SetOpStatePerGroup) fc_entry->additional, fc_flag);
		}
		else
		{
			/* 达到第二关系 */
			fc_in_first_rel = false;

			/* 对于之前未见的元组，不建立哈希表条目 */
			fc_entry = LookupTupleHashEntry(fc_setopstate->hashtable, fc_outerslot,
										 NULL, NULL);

			/* 如果条目已经存在，则提升计数 */
			if (fc_entry)
				fc_advance_counts((SetOpStatePerGroup) fc_entry->additional, fc_flag);
		}

		/* 必须在每次哈希表查找后重置表达式上下文 */
		ResetExprContext(fc_econtext);
	}

	fc_setopstate->table_filled = true;
	/* 初始化以遍历哈希表 */
	ResetTupleHashIterator(fc_setopstate->hashtable, &fc_setopstate->hashiter);
}

/*
 * ExecSetOp用于哈希情况：阶段2，从哈希表中检索组
 */
static TupleTableSlot * fc_setop_retrieve_hash_table(SetOpState *fc_setopstate)
{
	TupleHashEntryData *fc_entry;
	TupleTableSlot *fc_resultTupleSlot;

	/*
	 * 从节点获取状态信息
	 */
	fc_resultTupleSlot = fc_setopstate->ps.ps_ResultTupleSlot;

	/*
	 * 我们循环检索组，直到找到一个应该返回的
	 */
	while (!fc_setopstate->setop_done)
	{
		CHECK_FOR_INTERRUPTS();

		/* 
		 * 找到哈希表中的下一个条目
*/
		fc_entry = ScanTupleHashTable(fc_setopstate->hashtable, &fc_setopstate->hashiter);
		if (fc_entry == NULL)
		{
			/* 哈希表中没有更多条目，因此完成 */
			fc_setopstate->setop_done = true;
			return NULL;
		}

		/*
		 * 查看是否应发出此元组的任何副本，如果是，则返回
		 * 第一个副本。
		 */
		set_output_count(fc_setopstate, (SetOpStatePerGroup) fc_entry->additional);

		if (fc_setopstate->numOutput > 0)
		{
			fc_setopstate->numOutput--;
			return ExecStoreMinimalTuple(fc_entry->firstTuple,
										 fc_resultTupleSlot,
										 false);
		}
	}

	/* 没有更多组 */
	ExecClearTuple(fc_resultTupleSlot);
	return NULL;
}

/* ----------------------------------------------------------------
 *		ExecInitSetOp
 *
 *		此函数初始化setop节点状态结构和
 *		节点的子计划。
 * ----------------------------------------------------------------
 */
SetOpState *
ExecInitSetOp(SetOp *fc_node, EState *fc_estate, int fc_eflags)
{
	SetOpState *fc_setopstate;
	TupleDesc	fc_outerDesc;

	/* 检查不支持的标志 */
	Assert(!(fc_eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));

	/*
	 * 创建状态结构
	 */
	fc_setopstate = makeNode(SetOpState);
	fc_setopstate->ps.plan = (Plan *) fc_node;
	fc_setopstate->ps.state = fc_estate;
	fc_setopstate->ps.ExecProcNode = fc_ExecSetOp;

	fc_setopstate->eqfuncoids = NULL;
	fc_setopstate->hashfunctions = NULL;
	fc_setopstate->setop_done = false;
	fc_setopstate->numOutput = 0;
	fc_setopstate->pergroup = NULL;
	fc_setopstate->grp_firstTuple = NULL;
	fc_setopstate->hashtable = NULL;
	fc_setopstate->tableContext = NULL;

	/*
	 * 创建表达式上下文
	 */
	ExecAssignExprContext(fc_estate, &fc_setopstate->ps);

	/*
	 * 如果进行哈希处理，我们还需要一个寿命更长的上下文来存储哈希
	 * 表。该表不能仅保留在每个查询上下文中，因为
	 * 我们希望能够在ExecReScanSetOp中将其丢弃。
	 */
	if (fc_node->strategy == SETOP_HASHED)
		fc_setopstate->tableContext =
			AllocSetContextCreate(CurrentMemoryContext,
								  "SetOp hash table",
								  ALLOCSET_DEFAULT_SIZES);

	/*
	 * 初始化子节点
	 *
	 * 如果我们正在进行哈希处理，则子计划不需要有效地处理REWIND；
	 * 参见ExecReScanSetOp。
	 */
	if (fc_node->strategy == SETOP_HASHED)
		fc_eflags &= ~EXEC_FLAG_REWIND;
	outerPlanState(fc_setopstate) = ExecInitNode(outerPlan(fc_node), fc_estate, fc_eflags);
	fc_outerDesc = ExecGetResultType(outerPlanState(fc_setopstate));

	/*
	 * 初始化结果槽和类型。Setop节点不执行投影，因此
	 * 适当地初始化该节点的投影信息。
	 */
	ExecInitResultTupleSlotTL(&fc_setopstate->ps,
							  fc_node->strategy == SETOP_HASHED ?
							  &TTSOpsMinimalTuple : &TTSOpsHeapTuple);
	fc_setopstate->ps.ps_ProjInfo = NULL;

	/*
	 * 预计算内循环的fmgr查找数据。我们需要相等和
	 * 哈希函数以通过哈希处理，但如果不
	 * 进行哈希处理则只需要相等。
	 */
	if (fc_node->strategy == SETOP_HASHED)
		execTuplesHashPrepare(fc_node->numCols,
							  fc_node->dupOperators,
							  &fc_setopstate->eqfuncoids,
							  &fc_setopstate->hashfunctions);
	else
		fc_setopstate->eqfunction =
			execTuplesMatchPrepare(fc_outerDesc,
								   fc_node->numCols,
								   fc_node->dupColIdx,
								   fc_node->dupOperators,
								   fc_node->dupCollations,
								   &fc_setopstate->ps);

	if (fc_node->strategy == SETOP_HASHED)
	{
		fc_build_hash_table(fc_setopstate);
		fc_setopstate->table_filled = false;
	}
	else
	{
		fc_setopstate->pergroup =
			(SetOpStatePerGroup) palloc0(sizeof(SetOpStatePerGroupData));
	}

	return fc_setopstate;
}

/* ----------------------------------------------------------------
 *		ExecEndSetOp
 *
 *		此函数关闭子计划并释放分配给
 *		该节点的资源。
 * ----------------------------------------------------------------
 */
void ExecEndSetOp(SetOpState *fc_node)
{
	/* 清理元组表 */
	ExecClearTuple(fc_node->ps.ps_ResultTupleSlot);

	/* 释放附属内容，包括哈希表 */
	if (fc_node->tableContext)
		MemoryContextDelete(fc_node->tableContext);
	ExecFreeExprContext(&fc_node->ps);

	ExecEndNode(outerPlanState(fc_node));
}


void ExecReScanSetOp(SetOpState *fc_node)
{
	ExecClearTuple(fc_node->ps.ps_ResultTupleSlot);
	fc_node->setop_done = false;
	fc_node->numOutput = 0;

	if (((SetOp *) fc_node->ps.plan)->strategy == SETOP_HASHED)
	{
		/*
		 * 在哈希情况下，如果我们还没有构建哈希表，那么我们
		 * 只需返回；什么也没做，所以无须撤销。如果子节点的
		 * chgParam 不是 NULL，那么它将由 ExecProcNode 重新扫描，
		 * 否则完全没有理由重新扫描它。
		 */
		if (!fc_node->table_filled)
			return;

		/*
		 * 如果我们确实有哈希表，并且子计划没有任何
		 * 参数更改，那么我们可以只重新扫描现有的哈希表；
		 * 不需要再次构建它。
		 */
		if (fc_node->ps.lefttree->chgParam == NULL)
		{
			ResetTupleHashIterator(fc_node->hashtable, &fc_node->hashiter);
			return;
		}
	}

	/* 如果我们做了副本，则释放组的第一个元组 */
	if (fc_node->grp_firstTuple != NULL)
	{
		heap_freetuple(fc_node->grp_firstTuple);
		fc_node->grp_firstTuple = NULL;
	}

	/* 释放任何哈希表存储 */
	if (fc_node->tableContext)
		MemoryContextResetAndDeleteChildren(fc_node->tableContext);

	/* 如果需要，重建空哈希表 */
	if (((SetOp *) fc_node->ps.plan)->strategy == SETOP_HASHED)
	{
		ResetTupleHashTable(fc_node->hashtable);
		fc_node->table_filled = false;
	}

	/*
	 * 如果子节点的chgParam不为空，则计划将由第一个ExecProcNode重新扫描。
	 */
	if (fc_node->ps.lefttree->chgParam == NULL)
		ExecReScan(fc_node->ps.lefttree);
}
